/**
 * mLibTriangle.js
 * Created: May 2013
 * Source link: http://code.google.com/p/code-depository/source/browse/
 *
 * By Suresh Nalluri,
 * License: The MIT License (MIT)
 *          See LICENSE details
 *
 *	A collection of functions to manage triangles
 *
 *  Todo:
 *      - more efficient to do in-line coding for cross products, dot products etc. to speep up and to minimise
 *        object creation.
 *
 *-------------------------------------------------------
 **/
 
if (typeof mLIB == 'undefined') function mLIB() {};

( function(module) {

    module.Triangle = function() {};

	var Triangle = 	module.Triangle,
		Vec2 = module.Vec2,
		eZERO = module.Includes.ZERO,
		isZero = module.Includes.isZero,
		abs = module.Includes.abs,
		min = module.Includes.min,
		max = module.Includes.max;
	
	/**
	 * internal helper funcs
	**/
	
	// test if the 3 points T0, T1, T2 (making up a triangle T) are all outside the given edgevector
	// the edge vector defines an edge of the other triangle
	function edgeTest(edgePoint, edgeVec, signedNormalLength, T0, T1, T2) {
		// returns tru if all T's points are on the outside of the edge
		// note signedNormalLength gives the size of the normal at edgePoint
		// we're only interested whether it's -ve or +ve
		//

		if  ( signedNormalLength * edgeVec.perpDot(T0.Minus(edgePoint)) > 0.0 ) return false;	// test T0 against the edge
		if  ( signedNormalLength * edgeVec.perpDot(T1.Minus(edgePoint)) > 0.0 ) return false;	// test T1 against the edge
		if  ( signedNormalLength * edgeVec.perpDot(T2.Minus(edgePoint)) > 0.0 ) return false;	// test T2 against the edge
		return true;

	};	//edgeTest()
	
	// helper func for 3D triangleIntersect function.
	// projects the 2 triangles to the same plane and tests if the projected triangles intersect 
	function coplanarTriangleIntersect(P0, P1, P2, Q0, Q1, Q2, normal) {
		var absNx = abs(normal.getX()),
			absNy = abs(normal.getY()),
			absNz = abs(normal.getZ()),
			pP0 = Vec2(), pP1 = Vec2(), pP2 = Vec2(),
			pQ0 = Vec2(), pQ1 = Vec2(), pQ2 = Vec2();
		
		// map the triangles to the plane which has the dimension with the biggest value in the normal dropped
		// eg. if |normal.x| > |normal.y| and |normal.x| > |normal.z|, then drop the x dimension
		
		if ( absNx > absNy && absNx > absNz)
		{
			// the x direction has largest magnitude, so drop this dimension
			pP0.set( P0.getY(), P0.getZ() );
			pP1.set( P1.getY(), P1.getZ() );
			pP2.set( P2.getY(), P2.getZ() );
			pQ0.set( Q0.getY(), Q0.getZ() );
			pQ1.set( Q1.getY(), Q1.getZ() );
			pQ2.set( Q2.getY(), Q2.getZ() );
		}
		else if ( absNy > absNx && absNy > absNz)
		{
			// the y direction has largest magnitude, so drop this dimension
			pP0.set( P0.getX(), P0.getZ() );
			pP1.set( P1.getX(), P1.getZ() );
			pP2.set( P2.getX(), P2.getZ() );
			pQ0.set( Q0.getX(), Q0.getZ() );
			pQ1.set( Q1.getX(), Q1.getZ() );
			pQ2.set( Q2.getX(), Q2.getZ() );
		} 
		else
		{
			//the z direction has largest magnitude, so drop this dimension
			pP0.set( P0.getX(), P0.getY() );
			pP1.set( P1.getX(), P1.getY() );
			pP2.set( P2.getX(), P2.getY() );
			pQ0.set( Q0.getX(), Q0.getY() );
			pQ1.set( Q1.getX(), Q1.getY() );
			pQ2.set( Q2.getX(), Q2.getY() );
		}

		return triangleIntersectTriangle2D(pP0, pP1, pP2, pQ0, pQ1, pQ2);
		
	};	//coplanarTriangleIntersect()

	// helper func for triangleIntersectTriangle3D
	// test to see if the P's line segment overlaps Q's line segment.  Both line segments are on the line
	// of intersection of their respective supporting planes.  
	function isOverlap(Q0, Q1, Q2, P0, P1, P2) {

		// [Q1, P1, Q0, P0]	< 0 ?
		var normal = P1.Minus(P0).cross(Q0.Minus(P0));
		if ( normal.dot(Q1.Minus(P0)) > eZERO ) return false;	// no overlap
		
		// [Q0, P2, Q2, P0] < 0 ??
		normal = P2.Minus(P0).cross(Q2.Minus(P0));
		if (normal.dot(Q0.Minus(P0)) > eZERO ) return false;	// no overlap
		
		return true;  // overlaps
		
	};	//isOverlap()
	
	// Helper func for triangleIntersectTriangle3D
	// we use Q as the reference triangle here and reorder P's vertices accordingly and test for overlap
	function testFromQsPerspective(P0, P1, P2, Q0, Q1, Q2, sdQ0, sdQ1, sdQ2, piPnormal) {
		// this is essentially a mirror reflection of triangleIntersectTriangle3D, with P & Q swapping
		//
		if (sdQ0 > eZERO) {
			// Q0 in +ve P - now look for the lone vertex
			if (sdQ1 > eZERO) {
				//Q1 in +ve P => Q2 is the lone vertex and in -ve P by default
				return isOverlap(Q2, Q0, Q1, P0, P2, P1);
				
			} if (sdQ2 > eZERO) {
				//Q2 in +ve P => Q1 is the lone vertex and in -ve P by default
				return isOverlap(Q1, Q2, Q0, P0, P2, P1);
				
			} else {
				//Q1 & Q2 in -ve P or on P's plane => Q0 is the lone vertex and in +ve P!!
				return isOverlap(Q0, Q1, Q2, P0, P1, P2);

			}
		} else if (sdQ0 < -eZERO) {
			// P0 in -ve Q - now look for the lone vertex
			if (sdQ1 < -eZERO) {
				//P1 in -ve Q => P2 is lone and in +ve Q by default
				return isOverlap(Q2, Q0, Q1, P0, P1, P2);
				
			} else if ( sdQ2 < -eZERO) {
				//P2 in -ve Q => P1 is lone and in +ve Q by default
				return isOverlap(Q1, Q2, Q0, P0, P1, P2);
				
			} else {
				//P1 & P2 in +ve Q or on Q's plane => P0 is lone and in -ve Q by default
				return isOverlap(Q0, Q1, Q2, P0, P2, P1);
			}
			
		} else {
			// Q0 lies on P's plane - check each of Q1 & Q2
			if (sdQ1 > eZERO) {
				//Q1 in +ve P
				if (sdQ2 > eZERO) {
					// Q1 & Q2 in +ve P0 => Q0 is lone vertex on P's plane and -ve P by default
					return isOverlap(Q0, Q1, Q2, P0, P2, P1);
					
				} else {
					// Q2 in -ve P or on P's plane => Q1 is lone vertex and +ve P
					return isOverlap(Q1, Q2, Q0, P0, P1, P2);
					
				}
			} else if (sdQ1 < -eZERO) {
				//Q1 in -ve P
				if (sdQ2 < -eZERO) {
					//Q2 in -ve P => Q0 is lone vertex and +ve P by default
					return isOverlap(Q0, Q1, Q2, P0, P1, P2);
					
				} else {
					//Q2 in +ve P or on P's plane => Q1 is lone vertex and considered -ve P
					return isOverlap(Q1, Q2, Q0, P0, P2, P1);
				}
				
			} else {
				//Q1 lies on P's plane and so does Q0 remember- check Q2
				if (sdQ2 > eZERO) {
					//Q2 in +ve P => Q2 is lone vertex
					return isOverlap(Q2, Q0, Q1, P0, P1, P2);

				} else if (sdQ2 < -eZERO) {
					//Q2 in -ve P => Q2 is lone vertex
					return isOverlap(Q2, Q0, Q1, P0, P2, P1);

				} else {
					// Q0, Q1, Q2 all lies on P's plane ie coplanar
					return coplanarTriangleIntersect(P0, P1, P2, Q0, Q1, Q2, piPnormal);
				}
			}
		}

	}; //testFromQsPerspective()

	/**
	 *external facing funcs
	**/
	
	// test if triangles P & Q intersect (2D space)
	// remember the principle of separating planes here
	function triangleIntersectTriangle2D(P0, P1, P2, Q0, Q1, Q2) {
		// assumes all vectors and points are of type Vec2.
		
		var v0 = P1.Minus(P0),
			v1 = P2.Minus(P1),
			signedNormalLength = v0.perpDot(v1);
		
		// test P against Q first ---------------
		if ( edgeTest(P0, v0, signedNormalLength, Q0, Q1, Q2) ) return false;	// test with P's edge 0
		if ( edgeTest(P1, v1, signedNormalLength, Q0, Q1, Q2) ) return false;	// test with P's edge 1

		var v2 = P0.Minus(P2);
		if ( edgeTest(P2, v2, signedNormalLength, Q0, Q1, Q2) ) return false;	// test with P's edge 2

		// now test Q against P  ---------------
		v0 = Q1.Minus(P0);
		v1 = Q2.Minus(P1);
		signedNormalLength = v0.perpDot(v1);
		
		if ( edgeTest(Q0, v0, signedNormalLength, P0, P1, P2) ) return false;	// test with Q's edge 0
		if ( edgeTest(Q1, v1, signedNormalLength, P0, P1, P2) ) return false;	// test with Q's edge 1

		var v2 = Q0.Minus(Q2);
		if ( edgeTest(Q2, v2, signedNormalLength, P0, P1, P2) ) return false;	// test with Q's edge 2

		return true;

	};	// triangleIntersectTriangle2D()
	
	// return true if ray intersects triangle
	function triangleIntersectRay3D(P0, P1, P2, ray, lp) {
		// we define the 2 edge vectors of triangle:
		//	e1 = P1 - P0
		//	e2 = P2 - P0
		// Remember that we can use P0 and e1, e2 in affine combination that spans the plane of the triangele
		//	T(u,v) = P0 + u*e1 + v*e2	==> T(u,v) = (1-u-v)P0 + uP1 + vP2
		// For a point (eg our intersection) to be inside the triangle we require
		//	u, v >=0 and u+v <=1
		//
		// now we have the ray's line equation as L(t) = Lo + t*Ld
		// which means that at the intersection we have: Lo + t*Ld = (1-u-v)P0 + uP1 + vP2
		// ==> Lo + t*Ld = P0 + u*e1 + v*e2  ==> Lo-P0 = -t*Ld + u*e1 + v*e2
		// which can be expressed as: AB = Lo-P0, where A is the matrix [ -Ld, e1, e2 ] and
		// B is the column matrix (t, u, v).
		//	ie				   + +
		//					   |t|
		//	   [ -Ld, e1, e2 ] |u|	= Lo-P0
		//					   |v|
		//					   + +
		//
		// we use cramer's rule here to solve for u, v, the barycentric coords of the intersection and t the line parameter

		var e1 = P1.Minus(P0),
			e2 = P2.Minus(P0),
			n = ray.direction.Cross(e2),
			a = e1.dot(n);

        // if a is zero then we either have no intersection or the ray is parallel to the triangle plane
        // and has infinite intersections
        if ( isZero(a) ) return false;
        
        // the denominator
        var f = 1.0 / a;
        
        // compute each barycentric coord in turn and check if it lies within the triangle
        var s = ray.origin.Minus(P0),
            u = f * s.dot(n);
        
        if ( u < 0.0 || u > 1.0 ) return false;	// intersection outside triangle

        var q = s.cross(e1),
            v = f * ray.direction.dot(q);

        if ( v < 0.0 || u+v > 1.0 ) return false;	// intersection outside triangle

        lp.t = f * e2.dot(q);	// line parameter
        return ( lp.t >= 0.0 );

	};  // triangleIntersectRay3D()
    
    function triangleIntersectRay3D_test(P0, P1, P2, ray, lp) {
		var u = P1.Minus(P0),
			v = P2.Minus(P0),
            n  = u.Cross(v);

        if ( isZero(n.lengthSquared()) ) return false;  // degenerate triangle
        
        var w0 = ray.origin.Minus(P0),
            a = -n.dot(w0),
            b = ray.direction.dot(n);
        
        // ray either is parallel to triangle plane or has no intersection
        if ( isZero(b) ) return false;
        
        // calc intersect point of ray with plane
        var r = a/b;
        
        // ray points away from plane
        if ( r < 0.0 ) return false;
        
        var I = ray.direction.ScaleUp(r).plus(ray.origin);  // I = Ro + r*Rd

        // I inside triangle?
        var uu = u.lengthSquared(),
            uv = u.dot(v),
            vv = v.lengthSquared(),
            w  = I.minus(P0),
            wu = w.dot(u),
            wv = w.dot(v),
            d = uv*uv - uu*vv;

        // get parametric coords and test
        var s = (uv * wv - vv * wu) / d;
        if (s < 0.0 || s > 1.0) return false;        // I is outside T

        var t = (uv * wu - uu * wv) / d;

        if (t < 0.0 || (s + t) > 1.0) return false; // I is outside T
        
        return true;
        
    }; // triangleIntersectRay3D_test()

	// returns true if triangle P and Q intersect
	// based on an article by Guigue and Devillers
	function triangleIntersectTriangle3D(P0, P1, P2, Q0, Q1, Q2) {
		//
		// we hae 2 triangles P & Q on their respective planes piP and piQ
		// each triangle is defined with a 'left turn', ie. the 3 vertices form a left turn
		// for eg. P0->P1->P2
		//
		// the +ve half space of a plane as that side of the plane into which the plane's normal n points.
		// conversely the other half is -ve
		//
		//			-ve half	|	+ve half
		//						|
		//					  Q0|----->n  ( = (Q1-Q0) x (Q2-Q0) )  with Q0, Q1, Q2 maintaining right-handedness
		//						|
		//						|
		//						piQ
		//
		//	Note that the normal n and the point Q0 defines the plane piQ !
		//
		
		// A couple of tests to look for mutual intersection of each triangle with the plane of the other
		// 1. test P's verticies against piQ (Q's plane).. classify the vertices against the piQ plane
		// ie. above or below..  test for the signed distances!!
		var piQnormal = Q1.Minus(Q0).cross(Q2.Minus(Q0)),
			sdP0 = piQnormal.dot(P0.Minus(Q0)),
			sdP1 = piQnormal.dot(P1.Minus(Q0)),
			sdP2 = piQnormal.dot(P2.Minus(Q0));

		// simple test to see if all distances have the same sign
		if ( sdP0*sdP1 > eZERO && sdP0*sdP2 > eZERO ) return false;		// no intersection all P's vertices all lie on one side of piQ
		
		// 2. test Q's verticies against piP (P's plane)..
		var piPnormal = P1.Minus(P0).cross(P2.Minus(P0)),
			sdQ0 = piPnormal.dot(Q0.Minus(P0)),
			sdQ1 = piPnormal.dot(Q1.Minus(P0)),
			sdQ2 = piPnormal.dot(Q2.Minus(P0));

		// simple test to see if all distances have the same sign
		if ( sdQ0*sdQ1 > eZERO && sdQ0*sdQ2 > eZERO ) return false;		// no intersection all Q's vertices all lie on one side of piP

		// if you're here then the triangles intersect each others *planes* ( but not necessarily themselves) on a common
		// line of intersection L between piP and piQ.
		// let'say P's intersection is given by the line segment Lp, and Q's as Lq
		// since both segments lie on the line L, our test now simply becomes a test for Lp & Lq overlap
		//
		// In what follows we work with P as the reference triangle ( why P? i hear you ask.. Well we need to choose one !! )
		// **so imagine your overall viewpoint is from P's +ve half space**
		//
		// if we assume that the triangles are not coplanar then we have the situation where each triangle
		// has exactly one of its vertices lying on one side of the other triangle’s supporting plane with
		// the two other vertices on the other side
		//
		// reorder the vertices to ensure we have right handedness
		// 1. arrange P's vertices such that the lone vertex is first,
		//    imagine you viewpoint is in P's +ve half, which means P's vertices will always be in counter-clockwise (cc)
		//    and cyclicly ordered (the only condition being the lone vertex will be the 1st one).
		//
		// 2. permute Q's verices such that they appear counterclockwise order to P0
		//    The order of Q's vertices varies, depending on your viewpoint, ie. P's lone vertex.  a) If it is in Q's +ve half,
		//	  the order is the normal cc and cyclic ordering with the 1st vertex being the lone vertex of Q in P's +ve half and
		//	  b) if viewpoint is from Q's -ve half space, then we  start with the lone vertex of Q and read the other two in a
		//    *clockwise* manner.
		//
		// eg. 
		// 		+ve sdPx: vertex Px is in Q's +ve space  ( Px is one of P0, P1, P2 )
		// 		-ve sdPx: vertex Px is in Q's -ve space		
		//
		// 		if sdP0 is lone vertex in Q's +ve space ==> [P0, P1, P2, Q0, Q1, Q2]
		// 		if sdP0 is lone vertex in Q's -ve space ==> [P0, P1, P2, Q0, Q2, Q1]
		//
		//  NB:	sdP0 = sdP1 = sdP2 == ZERO: P & Q are coplanar
		//
		// Phew !!!
		//
		
		if (sdP0 > eZERO) {
			// P0 in +ve Q - now look for the lone vertex
			if (sdP1 > eZERO) {
				//P1 in +ve Q => P2 is the lone vertex and in -ve Q by default
				return testFromQsPerspective(P2, P0, P1, Q0, Q2, Q1, sdQ0, sdQ2, sdQ1, piPnormal);
				
			} if (sdP2 > eZERO) {
				//P2 in +ve Q => P1 is the lone vertex and in -ve Q by default
				return testFromQsPerspective(P1, P2, P0, Q0, Q2, Q1, sdQ0, sdQ2, sdQ1, piPnormal);
				
			} else {
				//P1 & P2 in -ve Q or on Q's plane => P0 is the lone vertex and in +ve Q!!
				return testFromQsPerspective(P0, P1, P2, Q0, Q1, Q2, sdQ0, sdQ1, sdQ2, piPnormal);

			}
		} else if (sdP0 < -eZERO) {
			// P0 in -ve Q - now look for the lone vertex
			if (sdP1 < -eZERO) {
				//P1 in -ve Q => P2 is lone and in +ve Q by default
				return testFromQsPerspective(P2, P0, P1, Q0, Q1, Q2, sdQ0, sdQ1, sdQ2, piPnormal);
				
			} else if ( sdP2 < -eZERO) {
				//P2 in -ve Q => P1 is lone and in +ve Q by default
				return testFromQsPerspective(P1, P2, P0, Q0, Q1, Q2, sdQ0, sdQ1, sdQ2, piPnormal);
				
			} else {
				//P1 & P2 in +ve Q or on Q's plane => P0 is lone and in -ve Q by default
				return testFromQsPerspective(P0, P1, P2, Q0, Q2, Q1, sdQ0, sdQ2, sdQ1, piPnormal);
			}
			
		} else {
			// P0 lies on Q's plane - check each of P1 & P2
			if (sdP1 > eZERO) {
				//P1 in +ve Q
				if (sdP2 > eZERO) {
					// P1 & P2 in +ve Q => P0 is lone vertex on Q's plane and -ve Q by default
					return testFromQsPerspective(P0, P1, P2, Q0, Q2, Q1, sdQ0, sdQ2, sdQ1, piPnormal);
					
				} else {
					// P2 in -ve Q or on Q's plane => P1 is lone vertex and +ve Q
					return testFromQsPerspective(P1, P2, P0, Q0, Q1, Q2, sdQ0, sdQ1, sdQ2, piPnormal);
					
				}
			} else if (sdP1 < -eZERO) {
				//P1 in -ve Q
				if (sdP2 < -eZERO) {
					//P2 in -ve Q => P0 is lone vertex and +ve Q by default
					return testFromQsPerspective(P0, P1, P2, Q0, Q1, Q2, sdQ0, sdQ1, sdQ2, piPnormal);
					
				} else {
					//P2 in +ve Q or on Q's plane => P1 is lone vertex and considered -ve Q
					return testFromQsPerspective(P1, P2, P0, Q0, Q2, Q1, sdQ0, sdQ1, sdQ2, piPnormal);
				}
				
			} else {
				//P1 lies on Q's plane and so does P0 remember- check P2
				if (sdP2 > eZERO) {
					//P2 in +ve Q => P2 is lone vertex
					return testFromQsPerspective(P2, P0, P1, Q0, Q1, Q2, sdQ0, sdQ1, sdQ2, piPnormal);

				} else if (sdP2 < -eZERO) {
					//P2 in -ve Q => P2 is lone vertex
					return testFromQsPerspective(P2, P0, P1, Q0, Q2, Q1, sdQ0, sdQ2, sdQ1, piPnormal);

				} else {
					// P0, P1, P2 all lies on Q's plane ie coplanar
					return coplanarTriangleIntersect(P0, P1, P2, Q0, Q1, Q2, piPnormal);
				}
			}
		}
		
	};	// triangleIntersectTriangle3D()

	// get the signed distance between plane and triangle.
	// ie. return the smallest distance with sign.. the closest vertex distance or 0 if triangle
	// intersects the plane.
	function triangleClassify3D(P0, P1, P2, plane) {
		var d0 = plane.test(P0),
			d1 = plane.test(P1);
			
		if ( d0 * d1 < 0.0 ) return 0.0;
		
		var d2 = plane.test(P2);
		if ( d0 * d2 < 0.0 ) return 0.0;
		if ( d1 * d2 < 0.0 ) return 0.0;
		
		if ( d1 > 0.0) return min(d1, d2, d3);
		return max(d1, d2, d3);
	
	};	// triangleClassify3D()

	// get barycentric coords (s,t) of a point Q within a triangle (P0P1P2) in 2D space
	function baryCentricCoords2D(Q, P0, P1, P2) {
		// remember the following relationship between a cross product (3D) and perpendicular
		// dot product in 2D  ( this is for the 2D case, where u and v are 2D vectors)
		//
		//	vperp.w = ||vperp||.||w||.cos(90-theta) = ||vperp||.||w||.sin(theta) = ||v||.||w||.sin(theta)
		//
		//	||v x w|| = ||v||.|w||.sin(theta) = vperp.w
		//
		//  The parametric plane equation: P(s, t) = P0 + su + tv
		//	=> P(s,t) - P0 = su + tv		.. where P(s, t) is point Q
		//	=> Q - P0 = su + tv				.. set w as the vector (Q - P0)
		//	=> w = su + tv
		//	=> v x w = sv x u + tv x v = sv x u		( note we get 3D vectors here normal to the 2D plane)
		//	=> ||v x w|| = |s|.||v x u||   .. we know s is +ve since Q is inside the triangle
		//	=> s = ||v x w|| / ||v x u||	.. note that ||v x u|| = ||u x v||
		//	=> vperp.w = s.vperp.u	=> s = vperp.w / vperp.u
		//	similarly we can get t = ||u x w|| / ||u x v|| = ||u x w|| / ||v x u|| = uperp.w / vperp.u
		//
		
		var u = P1.Minus(P0),
			v = P2.Minus(P0),
			w = Q.Minus(P0),			
			dNom = 1.0 / u.perpDot(v),
			s = v.perpDot(w) * dNom,
			t = u.perpDot(w) * dNom;
		
		return { 
			s: s,
			t: t,
			r: 1.0 - s - t		// since we have an afine space.. s + t = 1.0
		};
	};	// baryCentricCoords2D()

	// get barycentric coords (s,t) of a point Q within a triangle (P0P1P2) in 3D space
    // note if Q is off the triangle plane, we get the coords of the projected point, which
    // may or may not make sense !!.
    //
	function baryCentricCoords(Q, P0, P1, P2) {
		//  The parametric plane equation: P(s, t) = P0 + su + tv   - a convex combo of u and v
		//	and by convex combo we mean that 0>= s,t <= 1.0
		//	=> P(s,t) - P0 = su + tv		.. where P(s, t) is point Q
		//	=> Q - P0 = su + tv				.. set w as the vector (Q - P0)
		//	=> w = su + tv
		//	=> v x w = sv x u + tv x v = sv x u
		//	=> ||v x w|| = |s|.||v x u||   .. we know s is +ve since Q is inside the triangle
		//	=> s = ||v x w|| / ||v x u||	.. note that ||v x u|| = ||u x v||
		//	similarly we can get t = ||u x w|| / ||u x v|| = ||u x w|| / ||v x u||
		//
		
		var u = P1.Minus(P0),
			v = P2.Minus(P0),
			w = Q.Minus(P0),			
			dNom = 1.0 / u.Cross(v).length();

		var	s = v.cross(w).length() * dNom,     // noye use of cross instead of Cross
			t = u.cross(w).length() * dNom;

		return {
			s: s,
			t: t,
			r: 1.0 - s - t		// since we have an afine space.. s + t = 1.0
		};
	
	};	// baryCentricCoords()

	// test if point Q inside triangle P0P1P2 in 2D space
	function isPointInTriangle2D(Q, P0, P1, P2) {
		var v0 = P1.Minus(P0),
			v1 = P2.Minus(P1),
			n = v0.perpDot(v1),		// triangle 'normal' = signed length of v0 x v1 ie. the normal vector
			
		wTest = v0.perpDot(Q.Minus(P0));	// = signed length of v0 x w1.  testing if sign is same as that of the normal, 
		if ( wTest * n < 0.0 ) return false;
		
		wTest = v1.perpDot(Q.Minus(P1));
		if ( wTest * n < 0.0 ) return false;

		var v2 = P0.Minus(P2);
		wTest = v2.perpDot(Q.Minus(P2));
		if ( wTest * n < 0.0 ) return false;

		return true;
	
	}; // isPointInTriangle2D()
	
	// test if point Q inside triangle P0P1P2 in 3D space
    // note if Q is off the triangle plane, this tests to see if projected point
    // is in within the triangle, which may or may not make sense !!.
    //
	function isPointInTriangle(Q, P0, P1, P2) {
		var v0 = P1.Minus(P0),
			v1 = P2.Minus(P1),
			n = v0.Cross(v1),
			
		wTest = v0.cross(Q.Minus(P0));
		if ( wTest.dot(n) < 0.0 ) return false;
		
		wTest = v1.cross(Q.Minus(P1));
		if ( wTest.dot(n) < 0.0 ) return false;

		var v2 = P0.Minus(P2);
		wTest = v2.cross(Q.Minus(P2));
		if ( wTest.dot(n) < 0.0 ) return false;
			
		return true;
	
	};	// isPointInTriangle()

	// externalise the public methods

	Triangle.triangleIntersect2D = triangleIntersectTriangle2D;
	Triangle.baryCentricCoords2D = baryCentricCoords2D;
	Triangle.isPointInTriangle2D = isPointInTriangle2D;
	
	Triangle.triangleClassify = triangleClassify3D;
	Triangle.triangleIntersect = triangleIntersectTriangle3D;
	Triangle.triangleIntersectRay = triangleIntersectRay3D;
	Triangle.baryCentricCoords = baryCentricCoords;
	Triangle.isPointInTriangle = isPointInTriangle;
	
} )(mLIB);